/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  // 处理递归边界
  if (n == 1) return 1;
  if (n == 2) return 2;
  // 进行递归计算
  return climbStairs(n - 1) + climbStairs(n - 2);
};
const f: Array<number> = [];
// 记忆化搜索
const climbStairsMemory = (n: number) => {
  if (n == 1) return 1;
  if (n == 2) return 2;
  if (f[n] === undefined) {
    f[n] = climbStairsMemory(n - 1) + climbStairsMemory(n - 2);
  }
  // 若f[n] 已经求解过,直接返回
  return f[n];
};
// 动态规划的解法
const climbStairsDynamic = (n: number) => {
  // 初始化状态数组
  const f: Array<number> = [];
  f[1] = 1;
  f[2] = 2;
  // 自底向上开始推演
  for (let index = 3; index <= n; index++) {
    f[index] = f[index - 1] + f[index - 2];
  }
  // 直到推演到f[n]
  return f[n];
};
/**
 * 冒泡排序
 */
// 生成冒泡排序算法
const bubbleSort = (arr: Array<number>) => {
  // 缓存数组长度
  const len = arr.length;
  //  外层循环用于控制从头到尾的比较+交换到底有多少轮
  for (let index = 0; index < len; index++) {
    // 内层循环用于完成每一轮遍历过程中的重复比较+交换
    for (let j = 0; j < len - 1; j++) {
      // 若相邻元素前面的数比后面的大
      if (arr[j] > arr[j + 1]) {
        // 交换相邻的元素
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}
// 数组元素交换
const swapArrayElement = (arr: Array<number>, i: number, j: number) => {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}
